#ifndef LIST_HH
#define LIST_HH 1
//#include <assert.h>
#include <click/config.h>
//CLICK_DECLS

//CLICK_DECLS
namespace SNCoding
{

#define LIST_HEAD_MARKER 0 /* ((T *) 1) */

#define sizetype unsigned

template <typename T > class List;


template <typename T>
class List_member {
public:

    /** @brief Construct an isolated List_member. */
    List_member(const T& value)
	: _next(0), _prev(0) ,_value(value){
    }

    /** @brief Return the next element in the list. */
    List_member<T > *next() {
		return _next;
    }
    /** @overload */
    const List_member<T > *next() const {
		return _next;
    }

    /** @brief Return the previous element in the list. */
    List_member<T > *prev() {
		return _prev != LIST_HEAD_MARKER ? _prev : 0;
    }
    /** @overload */
    const List_member<T > *prev() const {
		return _prev != LIST_HEAD_MARKER ? _prev : 0;
    }

    T* value() {
    	return &_value;
    }

   const T* value() const {
    	return &_value;
    }

    bool operator==(const T& x){
    	return _value==x;
    }

    bool operator==(const List_member<T >& x){
		return _value==x._value;
	}

private:

    List_member<T > *_next;
    List_member<T > *_prev;
    T _value;

    List_member(const List_member<T> &x){}
    List_member<T> &operator=(const List_member<T> &x){}
    template <typename X > friend class List;

};


/** @class List::const_iterator
 * @brief Const iterator type for List. */
template <typename T>
class List_const_iterator {
public:
	/** @brief Construct an invalid iterator. */
	List_const_iterator()
		: _x(0), _list(0) {
	}

	List_const_iterator(const List_const_iterator<T>& iter)
		: _x(iter._x), _list(iter._list) {
	}
protected:
	/** @brief Construct an iterator pointing at @a x. */
	List_const_iterator(List_member<T > * x)
		: _x(x), _list(0) {
	}
	/** @brief Construct an end iterator for @a list. */
	List_const_iterator(List<T > * list)
		: _x(0), _list(list) {
	}
	/** @brief Construct an iterator pointing at @a x in @a list. */
	List_const_iterator(List_member<T > *x, List<T > *list)
		: _x(x), _list(list) {
	}
public:

	/** @brief Return the current list element or null. */
	const T *operator->() const {
		return _x->value();
	}
	/** @brief Return the current list element. */
	const T &operator*() const {
		return *(_x->value());
	}
	/** @brief Advance this iterator to the next element. */
	void operator++() {
		assert(_x);
		_x = _x->next();
	}
	/** @brief Advance this iterator to the next element. */
	void operator++(int) {
		++(*this);
	}
	/** @brief Advance this iterator to the previous element. */
	void operator--() {
		assert(_x);
		_x = _x->prev();
	}
	/** @brief Advance this iterator to the previous element. */
	void operator--(int) {
		--(*this);
	}

	void operator=(const List_const_iterator<T>& x){
		_x=x._x;
		_list=x._list;
	}

	/** @brief Test if this iterator equals @a x. */
	bool operator==(const List_const_iterator<T>& x) const {
		if(_list!=x._list) return false;
		return _x == x._x;
	}
	/** @brief Test if this iterator does not equal @a x. */
	bool operator!=(const List_const_iterator<T>& x) const {
		if(_list!=x._list) return true;
		return _x != x._x;
	}

	/** @brief Return the current list element or null. */
	const List_member<T > *get() const {
		return _x;
	}
protected:

	List_member<T >* _x;
	List<T >* _list;
	template <typename X > friend class List;
};

/** @class List::iterator
 * @brief Iterator type for List. */
template <typename T>
class List_iterator : public List_const_iterator<T> {
public:
	/** @brief Construct an invalid iterator. */
	List_iterator():
		List_const_iterator<T>() {
	}

	List_iterator(const List_iterator<T>& iter):
		List_const_iterator<T>(iter){}

private:
	/** @brief Construct an iterator pointing at @a x. */
	List_iterator(List_member<T > *x):
		List_const_iterator<T>(x) {
	}
	/** @brief Construct an end iterator for @a list. */
	List_iterator(List<T > *list):
		List_const_iterator<T>(list) {
	}
	/** @brief Construct an iterator pointing at @a x in @a list. */
	List_iterator(List_member<T > *x, List<T > *list):
		List_const_iterator<T>(x, list) {
	}



public:

	List_member<T > *get() {
		return this->_x;
	}
	
	/** @brief Return the current list element or null. */
	T *operator->()  {
		return this->_x->value();
	}
	/** @brief Return the current list element. */
	T &operator*()  {
		return *(this->_x->value());
	}
	template <typename X > friend class List;
};

#define MAX 10000

template <typename T >
class List {
public:

    typedef List_const_iterator<T> const_iterator;
    typedef List_iterator<T> iterator;
    /** @brief Construct an empty list. */
    List():
    	_head(0), _tail(0),_size(0),_capcity(MAX) {
    }

    List(sizetype cap):
		_head(0), _tail(0),_size(0),_capcity(cap) {
	}

    ~List(){
    	clear();
    }


    /** @brief Return an iterator for the first element in the list. */
    iterator begin() {
		return iterator(_head, this);
    }
    /** @overload */
    const_iterator begin() const {
		return const_iterator(_head, this);
    }
    /** @brief Return an iterator for the end of the list.
     * @invariant end().live() == false */
    iterator end() {
		return iterator(0,this);
    }
    /** @overload */
    const_iterator end() const {
		return const_iterator(0,this);
    }


    /** @brief Return true iff size() == 0.
     * @note Always O(1) time, whereas size() takes O(N) time. */
    bool empty() const {
		return _head == 0;
    }

    /** @brief Return the number of elements in the list.
     * @note Takes O(N) time, where N is the number of elements. */
    sizetype size() const {
    	return _size;
    }


    /** @brief Return the first element in the list.
     *
     * Returns a null pointer if the list is empty. */
    T& front() {
    	assert(_head!=0);
    	return *(_head->value());
    }
    /** @overload */
    const T& front() const {
    	assert(_head!=0);
		return *(_head->value());
    }
    /** @brief Return the last element in the list.
     *
     * Returns a null pointer if the list is empty. */
    T& back() {
    	assert(_tail!=0);
    	return *(_tail->value());
    }
    /** @overload */
    const T& back() const {
    	assert(_tail!=0);
		return *(_tail->value());
    }


    /** @brief Insert a new element at the beginning of the list.
     * @param x new element
     * @pre isolated(@a x) */
    iterator push_front(const T& x);

    /** @brief Insert a new element at the end of the list.
     * @param x new element
     * @pre isolated(@a x) */
    iterator push_back(const T& x);

    /** @brief Remove the element at the beginning of the list.
     * @pre !empty() */
    void pop_front();

    /** @brief Remove the element at the end of the list.
     * @pre !empty() */
    void pop_back() ;

private:
    /** @brief Insert an element before @a pos.
     * @param pos position to insert (if null, insert at end of list)
     * @param x new element
     * @pre (!@a pos || contains(@a pos)) && isolated(@a x) */
    iterator insert(List_member<T >* pos, const T& x) ;

    /** @brief Remove @a x from the list.
     * @param x element to remove
     * @pre contains(@a x) */


public:

	iterator find(const T& x){
		for(iterator iter=this->begin();iter!=this->end();++iter){
			if(*iter==x) return iter;
		}
		return this->end();
	}

    /** @brief Insert an element before @a it.
	 * @param it position to insert
	 * @param x new element
	 * @return an iterator pointing to @a x
	 * @pre isolated(@a x) */
	iterator insert(iterator& it,const  T& x) ;//{
		//insert(it.get(), x);
		//return iterator(x);
	//}

	bool erase(const T& x){
		iterator iter=find(x);
		if(iter==this->end()) return false;
		return erase(iter);
	}

	bool erase(List_member<T >* x) ;

	/** @brief Remove the element pointed to by @a it from the list.
	 * @param it element to remove
	 * @return iterator pointing to the element after the removed element
	 * @pre @a it.live() */
	bool erase(iterator& it) {
		//assert(it);
		//iterator next = iterator(it.get()->next(),this);
		return erase(it.get());
		//return next;
	}

	 /** @brief Remove the elements in [@a first, @a last) from the list.
	 * @param first iterator to beginning of removal subsequence
	 * @param last iterator to end of removal subsequence
	 * @return iterator pointing to the element after the removed subsequence */
	iterator erase(iterator& first, iterator& last) {
		while (first != last)
			first = erase(first);
		return first;
	}

	/** @brief Remove all elements from the list.
	 * @note Equivalent to erase(begin(), end()). */
	void clear() {
		while (List_member<T > *x = _head) {
			_head = x->_next;
			delete x;
		}
		_size=0;
		_head=_tail=0;
	}

	 /** @brief Exchange list contents with list @a x. */
	void swap(List<T > &x) {
		List_member<T > *h = x._head, *t = x._tail;
		x._head = _head, x._tail = _tail;
		_head = h, _tail = t;
	}

	/** @brief Check if @a x is a member of this list. */
	bool contains(const T& x) const {
		for (List_member<T > *it = _head; it; it = it->_next){
			if(*(it->value())==x) return true;
		}
		return false;
	}

	void set_capcity(int size){
		_capcity=size;
	}


private:

    List_member<T > *_head;
    List_member<T > *_tail;
    sizetype	_size;
    sizetype	_capcity;

    //List(const List<T > &x);
    List<T > &operator=(const List<T > &x);

};
}
//CLICK_ENDDECLS
#include "list.cc"
//#undef LIST_HEAD_MARKER
#endif
